package com.wuyou.mid;

import java.time.LocalDateTime;
import java.util.Date;

/**
 * CountPalindromicSubsequence
 *
 * @Date 2025-11-21 10:40
 * @Author 无忧
 */
public class CountPalindromicSubsequence {

    public static void main(String[] args) {

        String[] sArr = {"aabca", "adc", "bbcbaba", "tlpjzdmtwderpkpmgoyrcxttiheassztncqvnfjeyxxp",
                "bgpjrthbpdjvptqjlzkbggicrwcenarknkamaioicmrfmvrehzfqzbwfghouqyspphonljbvnhrikgnrowqnemrvygqvwxysbfmgttvkwxqvgherggdauimzkxfhauhoqbsubxihbyxrxkvvgondrpunmcpuivtutyfcfhkwbnscomghudmjiqxatubxrgkqsxrnglayyxhythwelivquhcumtyikxcegbksoistqelqafhocgstqdpkylwdepihcjkjvoaaopfcmgwbqpdyeoanuyvmffyvgtjlffvseeuazglgpqcmwzkfjlpbobymjprusvanjzrdxbeemimcslgizmzhjlxgvynletmyoxqlebememdxmlzolcsdjfhvtvorfzatexgmcihzdjycialsmqhribqlyzxudwuhutopcggukafkkqyehutxxpjcjflkgpckjeqcnzrqsynqcmcuhzrhglooxnnkmsvjptatmuvbksistlvixvfczgrlakarlkrtshvqrzrucdevseamdgvwocudkdxtlmalghvkicwlkmptzaknsyxwgbaoogqxdqqllesmlnprxwsmwskkyqjmzefrcmeemuymgoz",
                "aaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwxxxyyyzzzaaabbbcccdddeeefffggghhhiiijjjkkklllmmmnnnooopppqqqrrrssstttuuuvvvwwwxxxyyyzzz"};
        for (int i = 0; i < sArr.length; i++) {
            System.out.println(new CountPalindromicSubsequence().sol_2(sArr[i]));
        }
    }

    public int sol_2(String s) {
        int[][] record = new int[26][26];
        int[] beginC = new int[26];
        char[] chars = s.toCharArray();
        int length = s.length(), l = 0, r = 0, res = 0;
        while (l < length - 2) {
            if (beginC[chars[l] - 'a'] == 0) {
                r=s.lastIndexOf(chars[l]);
                if (r!=-1) {
                    beginC[chars[l] - 'a'] = 1;
                    for (int i = l+1; i < r; i++) {
                        if (record[chars[l] - 'a'][chars[i] - 'a'] == 0) {
                            res++;
                            record[chars[l] - 'a'][chars[i] - 'a'] = 1;
                        }
                    }
                }
            }
            l++;
        }
        return res;
    }
    public int sol_1(String s) {
        int[][] record = new int[26][26];
        int[] beginC = new int[26];
        char[] chars = s.toCharArray();
        int length = s.length(), l = 0, mid = 1, r = length - 1, res = 0;
        while (l < length - 2) {
            if (beginC[chars[l] - 'a'] == 0) {
                while (r > mid && chars[l] != chars[r]) {
                    r--;
                }
                if (chars[l] == chars[r]) {
                    beginC[chars[l] - 'a'] = 1;
                    for (int i = mid; i < r; i++) {
                        if (record[chars[l] - 'a'][chars[i] - 'a'] == 0) {
                            res++;
                            record[chars[l] - 'a'][chars[i] - 'a'] = 1;
//                        System.out.println("第"+res+"个回文->"+(chars[l]+""+chars[i]+""+chars[r]));
//                    }else {
//                        System.out.println("重复->"+(chars[l]+""+chars[i]+""+chars[r]));
                        }
                    }
                }
            }
            l++;
            mid = l + 1;
            r = length - 1;
        }
        return res;
    }

}
